// 51.N皇后
package Leetcode_Second_Brush;

import java.util.ArrayList;
import java.util.List;

public class Solution051 {
    List<List<String>> result = new ArrayList<>();

    public List<List<String>> solveNQueens(int n) {
        boolean[] column = new boolean[n];
        boolean[] ltTorb = new boolean[2 * n - 1];
        boolean[] rtTolb = new boolean[2 * n - 1];
        backTrace(n, new ArrayList<>(), 0, column, ltTorb, rtTolb);
        return result;
    }

    private void backTrace(int n, ArrayList<int[]> list, int cur, boolean[] column,
                          boolean[] ltTorb, boolean[] rtTolb) {
        if (cur == n) {
            result.add(form(list, n));
            return;
        }
        for (int i = 0; i < n; i++) {
            if (column[i] || ltTorb[cur + i] || rtTolb[cur - i + n - 1])
                continue;
            list.add(new int[]{cur, i});
            column[i] = true;
            ltTorb[cur + i] = true;
            rtTolb[cur - i + n - 1] = true;
            backTrace(n, list, cur + 1, column, ltTorb, rtTolb);
            list.remove(list.size() - 1);
            column[i] = false;
            ltTorb[cur + i] = false;
            rtTolb[cur - i + n - 1] = false;
        }
    }

    private List<String> form(ArrayList<int[]> list, int n) {
        List<String> ans = new ArrayList<>();
        for (int[] queen : list) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < n; i++) {
                if (i == queen[1])
                    sb.append("Q");
                else
                    sb.append(".");
            }
            ans.add(sb.toString());
        }
        return ans;
    }
}
